//
//  Algorithms.m
//  Amaranth
//
//  Created by Jinxiao on 12-12-23.
//  Copyright (c) 2012年 debugeek. All rights reserved.
//

#import "Algorithms.h"

#import <Foundation/Foundation.h>

int *rollback_table(const char *pattern)
{
    size_t length = strlen(pattern);
    int *rollback = (int *)malloc(sizeof(int)*length);
    memset(rollback, 0, length);
    rollback[0] = -1;
    for(int i = 1; i < length; i++)
    {
        char prev_char = pattern[i - 1];
        int prev_rollback = i - 1;
        while(prev_rollback >= 0)
        {
            int prev_rollback_index = rollback[prev_rollback];
            if((prev_rollback_index == -1) || (prev_char == pattern[prev_rollback_index]))
            {
                rollback[i] = prev_rollback_index + 1;
                break;
            }
            else
            {
                prev_rollback = rollback[prev_rollback];
            }
        }
    }
    
    return rollback;
}

bool compare(const char *source, const char *pattern)
{
    if(!source|| !pattern)
    {
        return false;
    }
    
    if(source == pattern)
    {
        return true;
    }
    
    size_t source_length = strlen(source);
    size_t pattern_length = strlen(pattern);
    if(source_length == 0 || pattern_length == 0)
    {
        return false;
    }
    
    bool found = false;
    int *rollback = rollback_table(pattern);
    
    int index = 0;
    
    for(int i = 0; i < source_length;)
    {
        if((index == -1) || (source[i] == pattern[index]))
        {
            if(source[i] == pattern[index])
            {
                found = true;
            }
            
            i++;
            index++;
            if(index == pattern_length)
            {
                free(rollback);
                
                return true;
            }
        }
        else
        {
            // 如果没有任何匹配上的字串，则根据回溯表进行下一轮匹配
            if(!found)
            {
                index = rollback[index];
            }
            // 如果有匹配上的字串，在剩下的字串里进行下一轮匹配
            else
            {
                free(rollback);
                
                return compare(source + i, pattern + index);
            }
        }
    }
    
    free(rollback);
    
    return false;
}


BOOL equal(id obj1, id obj2) {

    if(obj1 == nil && obj2 == nil) {
        return YES;
    }

    else if(obj1 == nil) {
        return NO;
    }

    else if(obj2 == nil) {
        return NO;
    }

    else {
        return [obj1 isEqual:obj2];
    }

}